package mess;

import java.util.Arrays;

public class LeeCode_1140 {
    public static void main(String[] args) {
        int[] piles = new int[]{1,2,3,4,5,100};
        System.out.println(stoneGameII(piles));
    }

    private static int stoneGameII(int[] piles) {
        int len = piles.length;
        int[][] dp = new int[len][len + 1];
        int sum = 0;
        for (int i = len - 1; i >= 0 ; i--) {
            sum += piles[i];
            for (int M = len; M >= 1; M--){
                //能一次拿完
                if (i + 2 * M >= len){
                    dp[i][M] = sum;
                }
                //不能一次拿完
                else {
                    for (int x = 1; x <= 2 * M; x++) {
                        dp[i][M] = Math.max(dp[i][M], sum - dp[i + x][Math.max(x, M)]);
                    }
                }
            }
        }
        return dp[0][1];
    }
}
